/**
 * 外观数列
 *
 * 「外观数列」是一个数位字符串序列，由递归公式定义：
 * countAndSay(1) = "1"
 * countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
 * 行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。
 * 给定一个整数 n ，返回 外观数列 的第 n 个元素。
 *
 * 示例 1：
 * 输入：n = 4
 * 输出："1211"
 * 解释：
 * countAndSay(1) = "1"
 * countAndSay(2) = "1" 的行程长度编码 = "11"
 * countAndSay(3) = "11" 的行程长度编码 = "21"
 * countAndSay(4) = "21" 的行程长度编码 = "1211"
 *
 * 示例 2：
 * 输入：n = 1
 * 输出："1"
 * 解释：
 * 这是基本情况。
 *
 * 提示：
 * 1 <= n <= 30
 *
 * 进阶：你能迭代解决该问题吗？
 */

/**
 * 找规律哦, 我们看题目要求可以知道, 要我们求 n 次外观数列, 我们只要将每一次的
 * 求法给分开就好了, 一次一次的来求, 而每一的求的时候我们都会依赖上一次的外观数列,
 * 所以我们要将每一的外观数列给保存下来, 然后我们观察每个外观书数列的变化, 其实就是遍历
 * 一遍字符串的事, 把相同的字符全都求出来, 然后在拼接到字符数组中去, 就可以执行下一次的
 * 字符串拼接了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public String countAndSay(int n) {

        // 这里我们初始化开头的字符串
        String s = "1";

        // 因为第一次字符串是不会改变外形的, 所以我们对他减一
        for (int i = 0; i < n - 1; i++) {

            // 求外观数列, 并覆盖原来的字符串
            s = toChangeBody(s);
        }

        // 返回求得的最后的外观数列
        return s;
    }

    /**
     * 外观数列求法
     *
     * @param s 我们要求的原字符串
     * @return
     */
    private String toChangeBody (String s) {

        // 定义字符串拼接函数
        StringBuffer ret = new StringBuffer();

        // 求他的长度
        int n = s.length();

        // 转为字符数组
        char[] ss = s.toCharArray();

        // 这里因为要求长度, 所以我们用双指针来写
        for (int left = 0, right = 0; right < n; ) {

            // 求相同的函数, 循环里面循环, 及得要看是否越界
            while (right < n && ss[right] == ss[left]) {
                right++;
            }

            // 走到 这里就是不一样的字符了
            // 我们求长度
            int len = right - left;

            // 拼接长度和字符
            ret.append(len);
            ret.append(ss[left]);

            // 改变左边界
            left = right;
        }

        // 转字符串并返回
        return ret.toString();
    }
}